﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution5
    {

        public string LongestPalindrome(string s)
        {

            int len = s.Length;
            if (len == 1)
            {
                return s;
            }

            bool[][] dp = new bool[len][];
            for (int i = 0; i < len; i++)
            {

                dp[i] = new bool[len];
                dp[i][i] = true;

            }
            int max = 1;
            int startIndex = 0;
            for (int l = 2; l <= len; l++)
            {
                for (int start = 0; start < len; start++)
                {
                    int end = start + l - 1;

                    if (end < len)
                    {
                        if (s[start] == s[end])
                        {

                            if (l == 2)
                            {
                                dp[start][end] = true;
                            }
                            else
                            {
                                if (dp[start + 1][end - 1])
                                {
                                    dp[start][end] = true;
                                }


                            }
                        }
                        else
                        {
                            dp[start][end] = false;
                        }

                        if (dp[start][end])
                        {
                            if (l > max)
                            {
                                startIndex = start;
                                max = l;

                            }

                        }
                    }

                }
            }

            return s.Substring(startIndex, max);



        }
    }
}
